/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package wordtypecounter;

/**
 *
 * @author Luis José
 */
/**
 * Implements a top-down splay tree.
 * Available at http://www.link.cs.cmu.edu/splay/
 * Author: Danny Sleator <sleator@cs.cmu.edu>
 * This code is in the public domain.
 */

class BinaryNode
{
    BinaryNode(Word theword) {
        word = theword;
        left = right = null;
    }

    Word word;          // The data in the node
    BinaryNode left;         // Left child
    BinaryNode right;        // Right child
}

public class SplayTree implements WordSet
{
    private BinaryNode root;

    public SplayTree() {
        root = null;
    }

    /**
     * Insert into the tree.
     * @param x the item to insert.
     * @throws DuplicateItemException if x is already present.
     */
    public void add(Word word) {
	BinaryNode n;
	int c;
	if (root == null) {
	    root = new BinaryNode(word);
	    return;
	}
	splay(word);
	if ((c = word.compareTo(root.word)) == 0) {
	    //	    throw new DuplicateItemException(x.toString());	    
	    return;
	}
	n = new BinaryNode(word);
	if (c < 0) {
	    n.left = root.left;
	    n.right = root;
	    root.left = null;
	} else {
	    n.right = root.right;
	    n.left = root;
	    root.right = null;
	}
	root = n;
    }

    /**
     * Find an item in the tree.
     */
    public Word get(Word word) {
	if (root == null) return null;
	splay(word);
        if(root.word.compareTo(word) != 0) return null;
        return root.word;
    }

    /** this method just illustrates the top-down method of
     * implementing the move-to-root operation 
     */
    private void moveToRoot(Word word) {
	BinaryNode l, r, t, y;
	l = r = header;
	t = root;
	header.left = header.right = null;
	for (;;) {
	    if (word.compareTo(t.word) < 0) {
		if (t.left == null) break;
		r.left = t;                                 /* link right */
		r = t;
		t = t.left;
	    } else if (word.compareTo(t.word) > 0) {
		if (t.right == null) break;
		l.right = t;                                /* link left */
		l = t;
		t = t.right;
	    } else {
		break;
	    }
	}
	l.right = t.left;                                   /* assemble */
	r.left = t.right;
	t.left = header.right;
	t.right = header.left;
	root = t;
    }

    private static BinaryNode header = new BinaryNode(null); // For splay
    
    /**
     * Internal method to perform a top-down splay.
     * 
     *   splay(word) does the splay operation on the given word.
     *   If word is in the tree, then the BinaryNode containing
     *   that word becomes the root.  If word is not in the tree,
     *   then after the splay, word.root is either the greatest word
     *   < word in the tree, or the lest word > word in the tree.
     *
     *   This means, among other things, that if you splay with
     *   a word that's larger than any in the tree, the rightmost
     *   node of the tree becomes the root.  This property is used
     *   in the delete() method.
     */

    private void splay(Word word) {
	BinaryNode l, r, t, y;
	l = r = header;
	t = root;
	header.left = header.right = null;
	for (;;) {
	    if (word.compareTo(t.word) < 0) {
		if (t.left == null) break;
		if (word.compareTo(t.left.word) < 0) {
		    y = t.left;                            /* rotate right */
		    t.left = y.right;
		    y.right = t;
		    t = y;
		    if (t.left == null) break;
		}
		r.left = t;                                 /* link right */
		r = t;
		t = t.left;
	    } else if (word.compareTo(t.word) > 0) {
		if (t.right == null) break;
		if (word.compareTo(t.right.word) > 0) {
		    y = t.right;                            /* rotate left */
		    t.right = y.left;
		    y.left = t;
		    t = y;
		    if (t.right == null) break;
		}
		l.right = t;                                /* link left */
		l = t;
		t = t.right;
	    } else {
		break;
	    }
	}
	l.right = t.left;                                   /* assemble */
	r.left = t.right;
	t.left = header.right;
	t.right = header.left;
	root = t;
    }
}

